package leetcode.day_2020_12_14_12_21;

public class L_213 {
    public static void main(String[] args) {
        int[] nums = {114,117,207,117,235,82,90,67,143,146,53,108,200,91,80,223,58,170,110,236,81,90,222,
                160,165,195,187,199,114,235,197,187,69,129,64,214,228,78,188,67,205,94,205,169,241,202,144,240};
        System.out.println(Math.max(rob(nums, 0, nums.length-2), rob(nums, 1, nums.length-1)));
    }

    public static int rob(int[] nums, int start, int end) {
        if (nums.length == 0) {
            return 0;
        }else if (nums.length == 1) {
            return nums[0];
        }
        int dp_i_1 = 0, dp_i_2 = 0;
        int dp_i = 0;
        for(int i=end; i>=start; i--) {
            dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        return dp_i;
    }
}
